package middle;

/**
 * 给你一个下标从 1 开始的整数数组numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
 *
 * 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
 *
 * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
 *
 * 你所设计的解决方案必须只使用常量级的额外空间。
 *
 * 链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class TwoSumIIInputArrayIsSorted {
    /**
     * 有序的数组，这种一般能令人联想到二分查找法 或者 双指针法。
     * 对于本题，双指针法，似乎更加容易理解和实现
     * */
    class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int l = 1;
            int r = numbers.length-1;
            while(l < r){
                if(target == (numbers[l] + numbers[r])){
                    return new int[]{l+1,r+1};
                }
                if(target > (numbers[l] + numbers[r])){
                    l++;
                }else{
                    r--;
                }
            }
            // 没找到 应该是抛异常了！！！
            return new int[]{l+1,r+1};
        }
    }

    /**
     * 二分查找 + 双指针
     * 看了一下 时间复杂度超过100%的 答案代码。
     * 简直是太妙了 ！！！
     * 单纯按照二分查找无法满足所有case
     * 双指针在二分查找的基础上 做了一些查漏补缺。 这种组合搭配 妙啊！！！！
     * */
    class Solution1 {
        public int[] twoSum(int[] numbers, int target) {
            int l = 0;
            int r = numbers.length-1;
            while(l < r){
                int sum = numbers[l] + numbers[r];
                int mid = (r+l) >> 1;
                if(numbers[l]+numbers[mid] > target){
                    r = mid-1;
                }
                else if(numbers[r]+numbers[mid] < target){
                    l = mid+1;
                }
                else if(sum == target){
                    return new int[]{l+1,r+1};
                }
                else if (sum > target){
                    --r;
                }
                else {
                    ++l;
                }
            }
            return new int[]{-1,-1};
        }
    }

    class Solution2 {
        public int[] twoSum(int[] numbers, int target) {
            int left = 0;
            int right = numbers.length - 1;
            while(left < right){
                int sum = numbers[left] + numbers[right];
                int mid = (right + left) / 2;
                if(numbers[left] + numbers[mid] > target){
                    right = mid - 1;
                }else if(numbers[right] + numbers[mid] < target){
                    left = mid + 1;
                }else if(sum == target){
                    return new int[]{left + 1, right + 1};
                }else if(sum > target){
                    right--;
                }else{
                    left++;
                }
            }
            return new int[]{-1,-1};
        }
    }
}
